/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */

/**
 * 题目：相交链表
 * 思路：
 *      1.求出两个链表的长度，让长链表走差值步数，接着两者一起走，如果相遇，则两者相交，如果有一方遍历到空，那么两者不相交
 *      2.直接遍历看是否有相同的节点
 */
public class Test {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 先找出长的链表
        ListNode curl = headA;
        ListNode curs = headB;
        int lenA = 0;
        int lenB = 0;
        while (curl != null) {
            curl = curl.next;
            lenA++;
        }
        while (curs != null) {
            curs = curs.next;
            lenB++;
        }
        // 假设A长
        int len = lenA - lenB;
        curl = headA;
        curs = headB;
        if (len < 0) {
            len = -len;
            curl = headB;
            curs = headA;
        }
        // len 与 cur 一定是指向最长的了
        // 让最长的走差值步
        while (len-- > 0) {
            curl = curl.next;
        }
        // 两者一起走
        while (curl != null && curs != null) {
            if (curl == curs) {
                return curl;
            }
            curl = curl.next;
            curs = curs.next;
        }
        return null;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
